package xyz.robinbingo.leetcode.a20.b05.c10;

import java.util.HashMap;
import java.util.Map;

/**
 * Solution
 *
 * @author Robin
 * @date 2020/5/10 21:27
 **/
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        for (int i = p.val; i != root.val; i = parent.get(i).val) {
            for (int j = q.val; j != root.val; j = parent.get(j).val) {
                if (parent.get(j).val == parent.get(i).val) {
                    return parent.get(j);
                }
                if (parent.get(j).val == i) {
                    return parent.get(j);
                }
                if (parent.get(i).val == j) {
                    return parent.get(i);
                }
            }
        }
        return root;
    }

    Map<Integer, TreeNode> parent = new HashMap<>();

    private void dfs(TreeNode node) {
        if (node.left != null) {
            parent.put(node.left.val, node);
            dfs(node.left);
        }
        if (node.right != null) {
            parent.put(node.right.val, node);
            dfs(node.right);
        }
    }
}